package com.al.study.record.sort;

/**
 * Created by yuxi on 2017/9/1.
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};
        int[] sortList = shellSort(arr);
        for (int i : sortList) {
            System.out.print(i + "  ");
        }

    }

    /**
     * shell  sort
     *
     * @param arr
     * @return
     */
    private static int[] shellSort(int[] arr) {
        if (arr.length == 0) return null;
        // 计算出步长
        int h = 1;
        int N = arr.length;
        while (h < N / 3) h = (h * 3 + 1);
        //控制步长
        while (h >= 1) {
            //插入排序
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                    int temp = arr[j - h];
                    arr[j - h] = arr[j];
                    arr[j] = temp;
                }
            }
            h = h / 3;
        }
        return arr;
    }
}
